package leetcode.code1648;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	int mod = (int) 1e9 + 7;

	public int maxProfit(int[] inventory, int orders) {
		int max = 0;
		for (int element : inventory) {
			max = Math.max(max, element);
		}
		long l = 0, r = max;
		long cut = 0;
		while (l <= r) {
			long mid = l + ((r - l) >> 1);
			long sum = 0;
			for (long num : inventory) {
				if (num > mid) {
					long size = num - mid;
					sum += size;
				}
			}
			if (sum >= orders) {
				cut = mid;
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		long sum = 0;
		cut += 1;
		long ans = 0;
		for (long num : inventory) {
			if (num > cut) {
				long size = num - cut;
				sum += size;
				ans += ((num + cut + 1) * size / 2) % mod;
				ans %= mod;
			}
		}
		ans += ((orders - sum) * cut) % mod;
		ans %= mod;
		return (int) ans;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(110, this.maxProfit(HelpDebug.str2array3("[2,8,4,10,6]"), 20));

	}

	@Override
	public void debug2() {
		HelpDebug.compare(21, this.maxProfit(HelpDebug.str2array3("[1000000000]"), 1000000000));

	}

	@Override
	public void debug3() {
		HelpDebug.compare(70267492, this.maxProfit(HelpDebug.str2array3("[773160767]"), 252264991));

	}

	@Override
	public void debug4() {
		HelpDebug.compare(525803723, this.maxProfit(HelpDebug.str2array3(
				"[701695700,915736894,35093938,364836059,452183894,951826038,861556610,441929847,842650446,858413011,457896886,35119509,776620034,396643588,83585103,681609037]"),
				598226067));

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
//		[773160767]
//				252264991
	}

}
